\section{Implementation}


	\subsection{Execution sequence}
		
		Execution sequence is described on the following diagram :
		\begin{figure}[H]
			\centering
			\includegraphics[scale=0.56]{img/seq_diag.png}
			\caption{Sequence diagram : best action computation}
		\end{figure}
		
		First the program call the \textit{Alpha beta} algorithm which creates the search tree on-the-fly during its execution. That creation involves a call to a method \textit{getMoves()} which enumerates all possible player's moves according to the state of the board. When the desired depth is reached, the node utility is computed by the heuristic function and returned to parent node. When the search is completed, the best move is retrieved and the application just write the move on standard output. The output format if a move is available is defined as follow : \verb?(row,column)?, \verb?pass? otherwise.

	\subsection{Programming issues and solutions}

	The major problem we had to deal with has been \textit{heap overflow}. By increasing the depth of the search, i.e. the number of steps looked ahead, the search tree size becomes very large. Alphabeta pruning as presented before reduces search time, but not necessarily the tree size, which depends of the implementation.\\

	At first, steps were executed sequentially : building the all-possible-moves tree, and then evaluating the best action to do. It appears that this is obviously not optimum : most of the times, the algorithm stops before visiting all the tree, thanks to pruning. Thus, we change the algorithm to generate the nodes on the fly : children are created only if the algorithm needs them. This is done by adding a \textit{this.expandNode()} instruction before lines 7 and 17 of the previous algorithm (section \ref{alphabeta}).\\
	
	 This method reduces the heap size but do not completely prevent \textit{heap overflows}. To avoid these overflows, we used a trick to adjust the search depth according to the branching factor of the search tree root.

